import java.util.Arrays;

public class Recursion {
    //1.递归求 N 的阶乘
    public static int re1(int n) {
        if(n==1||n==0){
            return 1;
        }
        else{
            return n*re1(n-1);
        }
    }
    public static void main1(String[] args){
        System.out.println(re1(5));
    }

    //2.递归求 1 + 2 + 3 + ... + 10
    public static int re2(int sum2) {
        if(sum2==1){
            return 1;
        }
        else{
            return sum2+re2(sum2-1);
        }
    }
    public static void main2(String[] args) {
        System.out.println(re2(10));
    }

    //3.使用递归完成按顺序打印一个数字的每一位(例如 1234 打印出 1 2 3 4)
    public static  void re3(int num) {
        if(num/10==0){
            System.out.print(num+" ");
        }
        else{
            re3(num/10);
            System.out.print(num%10+" ");
        }
    }
    public static void main3(String[] args) {
        re3(123544);
    }

    //4.写一个递归方法，输入一个非负整数，返回组成它的数字之和
    public static int re4(int sum4) {
        if(sum4/10==0){
            return sum4;
        }
        else{
            int k=sum4%10;
            return k+re4(sum4/10);
        }
    }
    public static void main4(String[] args) {
        System.out.println(re4(6666));
    }

    //5.递归求斐波那契数列的第 N 项
    public static int re5(int n) {
        if(n==1||n==2){
            return 1;
        }
        else {
            return re5(n-2)+re5(n-1);
        }
    }
    public static void main5(String[] args) {
        System.out.println(re5(1));
        System.out.println(re5(2));
        System.out.println(re5(3));
        System.out.println(re5(4));
        System.out.println(re5(5));
        System.out.println(re5(6));
    }

    //6.递归求解汉诺塔问题
    //move用于把A上的a移到B上
    public static void move(char a,char b) {
        System.out.print(a+"->"+b+" ");
    }
    //hanoi用于解决汉诺塔问题（a通过b挪到c）
    public static void hanoi(int n,char a,char b,char c){
        if(n==1){
            move(a,c);
        }
        else{
            hanoi(n-1,a,c,b);
            move(a,c);
            hanoi(n-1,b,a,c);
        }
    }
    public static void main6(String[] args) {
        hanoi(1,'A','B','C');
        System.out.println();
        hanoi(3,'A','B','C');
        System.out.println();
        hanoi(5,'A','B','C');
        System.out.println();
    }

    //7.数组的定义相关
    public static void main7(String[] args) {
        //定义方式 动态初始化：数据类型[] 数组名=new 数据类型[数据元素个数];
        int[] arr1=new int[5];
        //静态初始化：数据类型[] 数组名=new 数据类型{data1,data2,...,data N};或 数据类型[] 数组名={data1,data2,...,data N};
        int[] arr2=new int[]{1,22,333};//等式右侧[]不能写个数，因为赋值后该数组会自动计算数组个数
        //采用静态初始化时，new+数据类型可以省略不写
        int[] arr3={1,2,3};
        //访问数组时注意不要越界访问，越界访问必报错
        //int n=arr1[5];//arr1下标最多到4，越界访问
        //求数组长度：数组名.length
        System.out.println("数组arr2长度为："+arr2.length);
        //动态初始化分步式写法
        int[] arr4;//数据类型[] 数组名;
        arr4=new int[4];//数组名=new 数据类型[数据元素个数] //new 数据类型不能省略
        //静态初始化分步式写法
        int[] arr5;//数据类型[] 数组名;
        arr5=new int[]{1,2,34};//数组名=new 数据类型[]{data1,data2,...,data N}; //new 数据类型不能省略
        //空指针异常NullPointerException:arr6指向null，没有对象，所以不存在长度，故报错
        int[] arr6=null;//System.out.println(arr6.length);
        //遍历arr2
        for (int i = 0; i <arr2.length ; i++) {
            System.out.println(arr2[i]);
        }
        //遍历数组的第二种方式for-each: for(数组类型 i:数组名){ System.out.println(i); }
        for (int i :arr2) {
            System.out.print(i+" ");
        }
        //遍历数组的第三种方式 导入包import java.utill.Arrays;
        String ret= Arrays.toString(arr2);//Arrays.toString(arr2)：把数组2转化为字符串
        System.out.println(ret);
    }

    //8.数组传参
    public static void fun1(int[] arr) {
        arr=new int[]{11,22,33};
    }
    public static void fun2(int[] arr) {
        arr[0]=99;
    }
    public static void main8(String[] args) {
        int[] arr=new int[]{1,2,3};
        //fun1(arr);
        fun2(arr);
        System.out.println(Arrays.toString(arr));
    }

    //9.实现整形数组转字符串
    public static String str (int[] arr) {
        String s="[ ";
        for (int i = 0; i <arr.length ; i++) {
            s+=arr[i]+" ";
        }
        s+="]";
        return s;
    }
    public static void main9(String[] args) {
        int[] arr1=new int[]{24,32,12,45};
        System.out.println(str(arr1));
    }

    //10.数组的拷贝
    public static void main10(String[] args) {
        int[] arr1=new int[]{2,3,4,5,6};
        //拷贝arr1这个数组，长度为arr1.length
        int[] copy=Arrays.copyOf(arr1,arr1.length);
        System.out.println(Arrays.toString(copy));
        //拷贝arr1这个数组，长度为arr1.length*2,前面内容不动，后面多的内容补0
        int[] copy2=Arrays.copyOf(arr1,arr1.length*2);
        System.out.println(Arrays.toString(copy2));
        //arr1扩容2倍
        arr1=Arrays.copyOf(arr1,arr1.length*2);
        System.out.println(Arrays.toString(arr1));
        //拷贝数组的一部分
        int[] copy3=Arrays.copyOfRange(arr1,1,3);//左闭右开[1,3)
        System.out.println(Arrays.toString(copy3));
        //使用clone进行拷贝
        int[] clone1=arr1.clone();
        System.out.println(Arrays.toString(clone1));
    }

    //11.数组的排序与查找
    public static void main11(String[] args) {
        int[] arr={25,1,35,14,8,99,42,101};
        //java自带查找工具Arrays.binarySearch(数组名,查找的元素);
        // 查找成功返回数组下标，查找失败返回负数
        System.out.println(Arrays.binarySearch(arr,99));
        //java中自带排序工具 Arrays.sort(数组名);空返回值
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    //12.数组的逆序
    public static void reverse(int[] arr) {
        int left=0;
        int right=arr.length-1;
        for (int k = 0; k <arr.length/2 ; k++) {
            int tmp=arr[left];
            arr[left]=arr[right];
            arr[right]=tmp;
            left++;
            right--;
        }
    }
    public static void main12(String[] args) {
        int[] arr={1,2,3,4,5,6,7,8,9};
        reverse(arr);
        System.out.println(Arrays.toString(arr));
    }

    //13.Arrays中常用工具
    public static void main13(String[] args) {
        int[] arr1={1,2,3,4,5,6,7,8,9};
        int[] arr={1,4,3,4,5,6,7,8,9};
        Arrays.equals(arr,arr1);//判断两个数组内容是否完全相等，返回值为布尔类型
        Arrays.fill(arr,99);//把arr数组中内容全部填充为99
        Arrays.fill(arr1,1,3,77);//把arr1中[1,3)的内容填充为77，局部填充
        System.out.println(Arrays.toString(arr1));
    }

    //14.二维数组：二维数组本质上也就是一维数组，只不过每个元素又是一个一维数组
    public static void main(String[] args) {
        //定义
        int[][] arr={{1,2,3},{4,5,6}};
        int[][] arr2=new int[][]{{1,2,3},{4,5,6}};
        int[][] arr3=new int[2][3];//2行3列
        //java中二维数组定义中可以省略列的
        int[][] arrr=new int[2][];
        arrr[0]=new int[3];//对每一个一维数组进行初始化
        arrr[1]=new int[5];//可以是不规则数组（各个行的元素个数不一定相同）
        //遍历数组，方法1
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(arr2[i][j]+" ");
            }
            System.out.println();
        }
        //验证二维数组的每个元素为一维数组
        System.out.println(arr2[0]);//[I@4554617c //为一维数组的地址
        System.out.println(arr2[1]);//[I@74a14482
        //二维数组的行数
        System.out.println(arr2.length);//2
        //二维数组的列数：二维数组中每个一维数组的元素个数
        System.out.println(arr2[0].length);//3
        System.out.println(arr2[1].length);//3
        //遍历数组，方法2；由二维数组的行列特性得知
        int[][] array = {{1,2,3,4,5,6,7,8,9,},{4,5,6}};
        for (int i = 0; i <array.length ; i++) {
            for (int j = 0; j <array[i].length ; j++) {
                System.out.print(array[i][j]+" ");
            }
            System.out.println();
        }
        //遍历数组，方法3
        for(int[] arrayy:array){
            for (int i:arrayy){
                System.out.print(i+" ");
            }
            System.out.println();
        }
        //深度打印二维数组
        String ret=Arrays.deepToString(array);//array是一个二维数组，存的是一维数组的地址，如果不加deep，那么打印的将会是地址
        System.out.println(ret);
    }

}
